1. Technical Field
The present disclosure relates to compute resource management and more specifically to managing free chains of compute resources such as computer memory.
2. Introduction
In a computer, the operating system and various user programs allocate and deallocate memory and other resources. Computers track which portions of memory are free using free chains. A free chain is essentially a linked list, or a chain of objects (such as portions of memory), each of which includes a pointer to the next object in the chain. For memory, the linked list includes at least one pointer within each memory location in the chain of objects which points to another memory location. Thus, an “object” in the list in the memory example of a free chain is a respective memory location and its associated pointer. A free chain can optionally include separate head and/or tail nodes or entries that do not represent an object. For example, the system could include a head node that is a pointer (i.e., no allocatable memory) that points to a first memory location.
When selecting an approach to manage free chains of memory, two opposing objectives are usually considered. The first objective is the desire to improve system performance by making efficient use of memory by using localized references. Localized references are references to objects which are temporally and/or spatially near to one another, such as in the same block of memory. Localized references improve system performance by reducing page faults, reducing swapping, and/or making caches operate more efficiently by reducing misses. A page fault is a message raised by software and sent to hardware signaling that the software is accessing a memory page that is mapped in address space but not loaded in physical memory. Properly managing locality can make up to a three-to-one difference in system performance.
The second objective with respect to managing free chains is the desire to improve system robustness by reducing the impact of programming bugs. A common programming bug occurs when a program continues to use and modify recently-freed memory. For example, consider when a pointer for object A and a pointer for object B both point to the same location in memory. If clear ownership is not established (and such establishment can be tricky), then calling the destructor for A cleans up B and vice versa. There is no problem if A cleans up B, or if B cleans up A. The problem comes if both things happen. If A cleans up B first, then B will access objects that A has already cleaned up which leads to the problem of the continued use and modification of recently-freed memory. A destructor is a routine that releases allocated memory, closes any open files, and performs general “cleanup” after a function finishes or in certain situations when a variable goes out of scope. The continued use and modification of recently freed memory can lead to computer system crashes.
A Most Recently Used (MRU) approach to managing the free chain addresses the first objective set forth above, while a Least Recently Used (LRU) approach addresses the second objective. Unfortunately, these two approaches contradict and are incompatible for simultaneous use, thus forcing an unattractive compromise between performance and robustness when managing free chains.